"""
题目：二叉树的坡度定义为 “该节点左子树所有节点
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_tilt(root):
    """计算二叉树的坡度（递归实现）"""
    total_tilt = 0  # 全局总坡度
    def dfs(node):
        nonlocal total_tilt
        if not node:
            return 0  # 空节点的子树和为0
        # 递归计算左右子树的节点值之和
        left_sum = dfs(node.left)
        right_sum = dfs(node.right)
        # 当前节点的坡度 = 左右子树和的绝对差，加入总坡度
        total_tilt += abs(left_sum - right_sum)
        # 返回当前节点及其子树的总节点值之和
        return node.val + left_sum + right_sum
    dfs(root)
    return total_tilt

def create_binary_tree(arr):
    if not arr:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    index = 1
    while queue and index < len(arr):
        current = queue.pop(0)
        if arr[index] is not None:
            current.left = TreeNode(arr[index])
            queue.append(current.left)
        index += 1
        if index < len(arr) and arr[index] is not None:
            current.right = TreeNode(arr[index])
            queue.append(current.right)
        index += 1
    return root

# 测试
# 树结构：
#       1
#      / \
#     2   3
root1 = create_binary_tree([1, 2, 3])
# 节点2坡度：0（无左右子树），节点3坡度：0，节点1坡度：|2-3|=1 → 总坡度1
print(find_tilt(root1))  # 输出: 1

# 树结构：
#        4
#       / \
#      2   9
#     / \   \
#    3   5   7
root2 = create_binary_tree([4, 2, 9, 3, 5, None, 7])
# 节点3：0，节点5：0，节点2：|3-5|=2；节点7：0，节点9：|0-7|=7；节点4：|(2+3+5)-(9+7)|=|10-16|=6 → 总坡度2+7+6=15
print(find_tilt(root2))  # 输出: 15